/*
 * Copyright (c) 2006 DSS Dev. Team
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 4. Neither the name of the DSS Team nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *      BTreeTest.cpp
 *
 * $DSS$
 */
// C Includes
#include <sys/time.h>
#include <stdio.h>
#include <stdlib.h>

// Local Includes
#include <BTree.hpp>
#include <STLVector.hpp>

template <typename T, FTSS::KeySize_t TreeWidth>class MemoryNodeStorage:
  public FTSS::NodeStorage<FTSS::BTreeNode<T, TreeWidth> >
{
public:
	// Create node storage
	FTSS::Result_t CreateStorage(FTSS::KeySize_t iMaxNodesCount) throw();
	// Set current root node ID
	void SetRootNodeId(const FTSS::BTreeNodeID_t & iNodeID)  throw();
	// Get current root node ID
	FTSS::BTreeNodeID_t GetRootNodeId() const throw();
	// Create a new B-Tree node and lock it
	FTSS::BTreeNode<T, TreeWidth> * CreateAndLock(FTSS::BTreeNodeID_t & iNodeID) throw();
	// Get and lock existing node
	FTSS::BTreeNode<T, TreeWidth> * GetAndLock(const FTSS::BTreeNodeID_t & iNodeID,  FTSS::LockMode_t iLockMode) throw();
	// Unlock node
	int Unlock(const FTSS::BTreeNodeID_t & iNodeID) throw();
	// Destroy Node
	int Destroy(const FTSS::BTreeNodeID_t & iNodeID) throw();
	// Synchonize node to the hard disk
	int Sync(const FTSS::BTreeNodeID_t & iNodeID) throw();
	// Constructor
	MemoryNodeStorage();
	// Destructor
	~MemoryNodeStorage() throw();
	// Debug level
	void Debug(const FTSS::Level_t & iLevel) throw();
	int iScore;
private:
	// Root Node ID
	FTSS::BTreeNodeID_t oRootNodeId;
	// Statistics
	int iLevel;

	int iDAScore;
	// DataStorage
	STLW::vector<FTSS::BTreeNode<T, TreeWidth> *> vStorage;

public:

void Score() throw()
{
	fprintf(stderr, "Lock/Unlock Score: %d\n",   iScore);
	fprintf(stderr, "Alloc/Dealloc Score: %d\n", iDAScore);
}

};

//
// Constructor
//
template <typename T, FTSS::KeySize_t TreeWidth> MemoryNodeStorage<T, TreeWidth>::MemoryNodeStorage(): iScore(0), oRootNodeId(0), iLevel(0), iDAScore(0) { ;; }

//
// Create node storage
//
template <typename T, FTSS::KeySize_t TreeWidth>
  FTSS::Result_t MemoryNodeStorage<T, TreeWidth>::CreateStorage(FTSS::KeySize_t iMaxNodesCount) throw() { return 0; }

//
// Set current root node ID
//
template <typename T, FTSS::KeySize_t TreeWidth>
  void MemoryNodeStorage<T, TreeWidth>::SetRootNodeId(const FTSS::BTreeNodeID_t & iNodeID) throw() { oRootNodeId = iNodeID; }

//
// Get current root node ID
//
template <typename T, FTSS::KeySize_t TreeWidth>
  FTSS::BTreeNodeID_t MemoryNodeStorage<T, TreeWidth>::GetRootNodeId() const throw() { return oRootNodeId; }

//
// Create a new B-Tree node and lock it
//
template <typename T, FTSS::KeySize_t TreeWidth>
  FTSS::BTreeNode<T, TreeWidth> * MemoryNodeStorage<T, TreeWidth>::CreateAndLock(FTSS::BTreeNodeID_t & iNodeID) throw()
{
	iScore++;
	iDAScore++;

	FTSS::BTreeNode<T, TreeWidth> * pNode = new FTSS::BTreeNode<T, TreeWidth>;
	vStorage.push_back(pNode);
	iNodeID = vStorage.size();
if (iLevel) { fprintf(stderr, "CreateAndLock: %p - %d\n", pNode, iNodeID); }
return pNode;
}

//
// Get and lock existing node
//
template <typename T, FTSS::KeySize_t TreeWidth>
  FTSS::BTreeNode<T, TreeWidth> * MemoryNodeStorage<T, TreeWidth>::GetAndLock(const FTSS::BTreeNodeID_t & iNodeID, FTSS::LockMode_t iLockMode) throw()
{
	iScore++;
if (iLevel) { fprintf(stderr, "GetAndLock: %p - %d\n", vStorage[iNodeID - 1], iNodeID); }
	return vStorage[iNodeID - 1];
}

//
// Unlock node
//
template <typename T, FTSS::KeySize_t TreeWidth>
  int MemoryNodeStorage<T, TreeWidth>::Unlock(const FTSS::BTreeNodeID_t & iNodeID) throw()
{
	iScore--;
if (iLevel) { fprintf(stderr, "Unlock: %d\n",  iNodeID); }
	return 0;
}

//
// Destroy Node
//
template <typename T, FTSS::KeySize_t TreeWidth>
  int MemoryNodeStorage<T, TreeWidth>::Destroy(const FTSS::BTreeNodeID_t & iNodeID) throw()
{
if (iLevel) { fprintf(stderr, "Destroy: %d\n",  iNodeID); }
	delete vStorage[iNodeID - 1];
	iDAScore--; iScore--;
	return 0;
}

//
// Synchonize node to the hard disk
//
template <typename T, FTSS::KeySize_t TreeWidth>
  int MemoryNodeStorage<T, TreeWidth>::Sync(const FTSS::BTreeNodeID_t & iNodeID) throw()
{
//fprintf(stderr, "Sync: %d\n",  iNodeID);
	return 0;
}

//
// Destructor
//
template <typename T, FTSS::KeySize_t TreeWidth>
  MemoryNodeStorage<T, TreeWidth>::~MemoryNodeStorage() throw()
{
	fprintf(stderr, "Lock/Unlock Score: %d\n",   iScore);
	fprintf(stderr, "Alloc/Dealloc Score: %d\n", iDAScore);
}

// Debug level
template <typename T, FTSS::KeySize_t TreeWidth>
  void MemoryNodeStorage<T, TreeWidth>::Debug(const FTSS::Level_t & iILevel) throw() { iLevel = iILevel; }

// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

template <typename T, FTSS::KeySize_t TreeWidth>
  void ShowTree(MemoryNodeStorage<T, TreeWidth> * pStorage, FTSS::BTreeNodeID_t oXId, int depth)
{

	FTSS::BTreeNode<T, TreeWidth> * x = pStorage -> GetAndLock(oXId, 0);
	// The number of keys in node
	int n_x = x -> key_count;

	if(!x -> is_leaf)
	{
		// This node is not a leaf so we must recurse down
		// BTreeNodeID_t
		ShowTree(pStorage, x -> children[n_x], depth+1);

	}
	// Else print all the keys in this node
	for(int i=n_x-1; i >= 0; i--)
	{
		for(int j=0; j < depth; j++) { printf("\t"); }
		printf("    %d\n", x -> keys[i]);

		// Now print any left children
		if (!x -> is_leaf) { ShowTree(pStorage, x -> children[i], depth+1); }
	}
	pStorage -> Unlock(oXId);
}

int main(void)
{
	MemoryNodeStorage<int, 5> oStorage;
	FTSS::BTree<int, 5> mytree(&oStorage);

	STLW::vector<int> vElements;

	srandom(time(NULL));
	printf("=== Fill tree =====================================\n");
	int * aElements = new int [1500];
	int iPrev  = 0;
	int iPrevT = 0;

	fprintf(stdout, "Duplicate keys: ");

	for (int i = 0; i < 1500; i++)
	{
		aElements[i] = iPrev + (random() & 0x7F);
		iPrev = aElements[i];

		if (iPrevT == iPrev) { fprintf(stdout, "%d ", iPrevT); }

		iPrevT = iPrev;
	}

	printf("\n");
	for (int i = 0; i < 1500; i++)
	{
		if (i != 0 && i % 50 == 0) { fprintf(stdout, "\n"); }

		fprintf(stdout, "%c", mytree.Insert(aElements[i]) ? '.':'!');
	}

#ifdef _SHOW_TREE
	printf("\n=== Print tree ====================================\n");
	ShowTree(&oStorage, oStorage.GetRootNodeId(), 0);
#endif // _SHOW_TREE

	printf("\n=== Search elements in tree =======================\n");
	for (int i = 0; i < 1500; i++)
	{
		if (i != 0 && i % 50 == 0) { fprintf(stdout, "\n"); }
		fprintf(stdout, "%c", mytree.Search(aElements[i]) == NULL ? '!':'.');
	}
	printf("\n=== Remove elements from tree =====================\n");
	for (int i = 0; i < 1500; i++)
	{
		if (i != 0 && i % 50 == 0) { fprintf(stdout, "\n"); }
		if (mytree.Remove(aElements[i]) == 0)
		{
			fprintf(stdout, "!");
			vElements.push_back(aElements[i]);
		}
		else { fprintf(stdout, "."); }
	}

	fprintf(stdout, "\nDuplicate keys: ");

	for (unsigned int i = 0; i < vElements.size(); i++) { fprintf(stdout, "%d ", vElements[i]); }
//	printf("\n");
//	ShowTree(&oStorage, oStorage.GetRootNodeId(), 0);
	printf("\n=== All done ======================================\n");
	delete [] aElements;
}
// End.
